'''
手写代码题：一个倒排有序的整数数组，将其分为 m 份，使各份的和相等，求 m 的最大值。
比如 {6，4，3，3，2} 
可以分成{6，4，3，3，2} m=1; 
{6,3} {4,3,2} m=2；
{6} {4,2} {3,3} m=3；
所以 m 的最大值为 3
（备注：请使用python语言，可以不处理输入直接定义常量数组，可以不考虑输出）
'''

# deepseek-r1 
def max_partition_m(arr):
    #arr = [6, 4, 3, 3, 2]  # 示例输入，已经是降序排列
    #arr = [3, 3, 3]
    total = sum(arr)
    n = len(arr)
    # 显式降序排列以确保正确性，即使输入可能已经排序
    arr.sort(reverse=True)
    # 从最大的可能m开始检查
    for m in range(n, 0, -1):
        if total % m != 0:
            continue
        target = total // m
        used = [False] * n  # 记录元素是否被使用过

        def backtrack(k, current_sum, start_idx):
            """
            k: 已经填满的桶的数量
            current_sum: 当前桶的累计和
            start_idx: 当前可选的元素起始索引
            """
            if k == m:
                return True
            if current_sum == target:
                # 当前桶已满，填下一个桶
                return backtrack(k + 1, 0, 0)
            # 从start_idx开始选元素，避免重复
            for i in range(start_idx, n):
                if not used[i] and current_sum + arr[i] <= target:
                    used[i] = True
                    if backtrack(k, current_sum + arr[i], i + 1):
                        return True
                    used[i] = False
                    # 剪枝：如果当前桶无法放入任何元素，则后续也不可能成功
                    if current_sum == 0:
                        return False
            return False

        if backtrack(0, 0, 0):
            return m
    return 1

# 测试用例
if __name__ == "__main__":    
    # 测试用例
    test_cases = [
        [6, 4, 3, 3, 2],
        [10, 8, 6, 4, 2],
        [7, 7, 7],
        [5, 4, 3, 2, 1],
        [5, 4, 3, 2],
    ]
    
    for i, test in enumerate(test_cases):
        print(f"测试用例 {i+1} {test}: 最大的m值为 {max_partition_m(test)}")